import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution_0347 {
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        //建立哈希表
        Map<Integer,Integer> map = new HashMap<>();
        //将数据放入哈希表
        for (int num:nums) {
          if (map.containsKey(num)){
              map.put(num,map.get(num)+1);
          }else{
              map.put(num,1);
          }
        }
        //建立优先队列
        PriorityQueue<Integer> queue = new PriorityQueue(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });
        //遍历哈希表，将数据放入优先队列
        for (Integer key : map.keySet()) {
            if (queue.size()<k){
                queue.add(key);
            }else if (map.get(key) > map.get(queue.peek())){
                //如果大于频率最小的，就将其弹出，然后添加进去
                queue.poll();
                queue.add(key);
            }
        }
        //将优先队列的结果拿出
        int i=0;
        while (!queue.isEmpty()){
            result[i++]=queue.poll();
        }
        return result;
    }
}
